package com.kexio.common.util;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 树形结构工具类
 * 
 * @author Kexio Team
 * @since 1.0.0
 */
public class TreeUtils {
    
    private TreeUtils() {
        // 工具类不允许实例化
    }
    
    /**
     * 树形节点接口
     */
    public interface TreeNode<T> {
        /**
         * 获取节点ID
         */
        T getId();
        
        /**
         * 获取父节点ID
         */
        T getParentId();
        
        /**
         * 获取子节点列表
         */
        List<? extends TreeNode<T>> getChildren();
        
        /**
         * 设置子节点列表
         */
        void setChildren(List<? extends TreeNode<T>> children);
        
        /**
         * 获取排序值
         */
        default Integer getSort() {
            return 0;
        }
    }
    
    /**
     * 构建树形结构
     * 
     * @param nodes 节点列表
     * @param rootValue 根节点的父ID值 (通常为null或0)
     * @param <T> 节点ID类型
     * @param <N> 节点类型
     * @return 树形结构列表
     */
    public static <T, N extends TreeNode<T>> List<N> buildTree(List<N> nodes, T rootValue) {
        if (nodes == null || nodes.isEmpty()) {
            return new ArrayList<>();
        }
        
        // 按父ID分组
        Map<T, List<N>> parentChildrenMap = nodes.stream()
            .collect(Collectors.groupingBy(TreeNode::getParentId));
        
        // 构建树形结构
        List<N> rootNodes = parentChildrenMap.getOrDefault(rootValue, new ArrayList<>());
        buildChildren(rootNodes, parentChildrenMap);
        
        // 排序
        sortTree(rootNodes);
        
        return rootNodes;
    }
    
    /**
     * 构建树形结构 (自动识别根节点)
     */
    public static <T, N extends TreeNode<T>> List<N> buildTree(List<N> nodes) {
        if (nodes == null || nodes.isEmpty()) {
            return new ArrayList<>();
        }
        
        // 收集所有ID
        Set<T> allIds = nodes.stream()
            .map(TreeNode::getId)
            .collect(Collectors.toSet());
        
        // 找出根节点 (parentId不在所有ID中的节点)
        List<N> rootNodes = nodes.stream()
            .filter(node -> node.getParentId() == null || !allIds.contains(node.getParentId()))
            .collect(Collectors.toList());
        
        // 按父ID分组
        Map<T, List<N>> parentChildrenMap = nodes.stream()
            .collect(Collectors.groupingBy(TreeNode::getParentId));
        
        // 构建子节点
        buildChildren(rootNodes, parentChildrenMap);
        
        // 排序
        sortTree(rootNodes);
        
        return rootNodes;
    }
    
    /**
     * 递归构建子节点
     */
    @SuppressWarnings("unchecked")
    private static <T, N extends TreeNode<T>> void buildChildren(List<N> parentNodes, Map<T, List<N>> parentChildrenMap) {
        if (parentNodes == null || parentNodes.isEmpty()) {
            return;
        }
        
        for (N parent : parentNodes) {
            List<N> children = parentChildrenMap.get(parent.getId());
            if (children != null && !children.isEmpty()) {
                parent.setChildren((List<? extends TreeNode<T>>) children);
                buildChildren(children, parentChildrenMap);
            }
        }
    }
    
    /**
     * 树形结构排序
     */
    private static <T, N extends TreeNode<T>> void sortTree(List<N> nodes) {
        if (nodes == null || nodes.isEmpty()) {
            return;
        }
        
        // 对当前层级排序
        nodes.sort(Comparator.comparing(TreeNode::getSort, Comparator.nullsLast(Integer::compareTo)));
        
        // 递归排序子节点
        for (N node : nodes) {
            List<? extends TreeNode<T>> children = node.getChildren();
            if (children != null && !children.isEmpty()) {
                @SuppressWarnings("unchecked")
                List<N> childList = (List<N>) children;
                sortTree(childList);
            }
        }
    }
    
    /**
     * 将树形结构转换为扁平列表
     */
    public static <T, N extends TreeNode<T>> List<N> treeToList(List<N> treeNodes) {
        if (treeNodes == null || treeNodes.isEmpty()) {
            return new ArrayList<>();
        }
        
        List<N> result = new ArrayList<>();
        for (N node : treeNodes) {
            result.add(node);
            List<? extends TreeNode<T>> children = node.getChildren();
            if (children != null && !children.isEmpty()) {
                @SuppressWarnings("unchecked")
                List<N> childList = (List<N>) children;
                result.addAll(treeToList(childList));
            }
        }
        return result;
    }
    
    /**
     * 在树中查找节点
     */
    public static <T, N extends TreeNode<T>> N findNode(List<N> treeNodes, T nodeId) {
        if (treeNodes == null || treeNodes.isEmpty() || nodeId == null) {
            return null;
        }
        
        for (N node : treeNodes) {
            if (nodeId.equals(node.getId())) {
                return node;
            }
            
            List<? extends TreeNode<T>> children = node.getChildren();
            if (children != null && !children.isEmpty()) {
                @SuppressWarnings("unchecked")
                List<N> childList = (List<N>) children;
                N found = findNode(childList, nodeId);
                if (found != null) {
                    return found;
                }
            }
        }
        return null;
    }
    
    /**
     * 获取节点的所有父节点路径
     */
    public static <T, N extends TreeNode<T>> List<N> getNodePath(List<N> allNodes, T nodeId) {
        if (allNodes == null || allNodes.isEmpty() || nodeId == null) {
            return new ArrayList<>();
        }
        
        // 创建ID到节点的映射
        Map<T, N> nodeMap = allNodes.stream()
            .collect(Collectors.toMap(TreeNode::getId, Function.identity()));
        
        List<N> path = new ArrayList<>();
        N currentNode = nodeMap.get(nodeId);
        
        while (currentNode != null) {
            path.add(0, currentNode); // 插入到开头，保证顺序是从根到当前节点
            T parentId = currentNode.getParentId();
            currentNode = parentId != null ? nodeMap.get(parentId) : null;
        }
        
        return path;
    }
    
    /**
     * 获取节点的所有子节点ID (包括自身)
     */
    public static <T, N extends TreeNode<T>> Set<T> getDescendantIds(List<N> treeNodes, T nodeId) {
        if (treeNodes == null || treeNodes.isEmpty() || nodeId == null) {
            return new HashSet<>();
        }
        
        Set<T> result = new HashSet<>();
        N targetNode = findNode(treeNodes, nodeId);
        
        if (targetNode != null) {
            collectDescendantIds(targetNode, result);
        }
        
        return result;
    }
    
    /**
     * 递归收集子节点ID
     */
    private static <T, N extends TreeNode<T>> void collectDescendantIds(N node, Set<T> result) {
        if (node == null) {
            return;
        }
        
        result.add(node.getId());
        
        List<? extends TreeNode<T>> children = node.getChildren();
        if (children != null && !children.isEmpty()) {
            for (TreeNode<T> child : children) {
                @SuppressWarnings("unchecked")
                N childNode = (N) child;
                collectDescendantIds(childNode, result);
            }
        }
    }
    
    /**
     * 获取树的最大深度
     */
    public static <T, N extends TreeNode<T>> int getMaxDepth(List<N> treeNodes) {
        if (treeNodes == null || treeNodes.isEmpty()) {
            return 0;
        }
        
        int maxDepth = 0;
        for (N node : treeNodes) {
            int depth = getNodeDepth(node, 1);
            maxDepth = Math.max(maxDepth, depth);
        }
        return maxDepth;
    }
    
    /**
     * 获取节点的深度
     */
    private static <T, N extends TreeNode<T>> int getNodeDepth(N node, int currentDepth) {
        if (node == null) {
            return currentDepth - 1;
        }
        
        List<? extends TreeNode<T>> children = node.getChildren();
        if (children == null || children.isEmpty()) {
            return currentDepth;
        }
        
        int maxChildDepth = currentDepth;
        for (TreeNode<T> child : children) {
            @SuppressWarnings("unchecked")
            N childNode = (N) child;
            int childDepth = getNodeDepth(childNode, currentDepth + 1);
            maxChildDepth = Math.max(maxChildDepth, childDepth);
        }
        
        return maxChildDepth;
    }
    
    /**
     * 过滤树节点
     */
    public static <T, N extends TreeNode<T>> List<N> filterTree(List<N> treeNodes, Function<N, Boolean> predicate) {
        if (treeNodes == null || treeNodes.isEmpty() || predicate == null) {
            return new ArrayList<>();
        }
        
        List<N> result = new ArrayList<>();
        
        for (N node : treeNodes) {
            N filteredNode = filterNode(node, predicate);
            if (filteredNode != null) {
                result.add(filteredNode);
            }
        }
        
        return result;
    }
    
    /**
     * 过滤单个节点
     */
    @SuppressWarnings("unchecked")
    private static <T, N extends TreeNode<T>> N filterNode(N node, Function<N, Boolean> predicate) {
        if (node == null || predicate == null) {
            return null;
        }
        
        // 递归过滤子节点
        List<? extends TreeNode<T>> children = node.getChildren();
        List<N> filteredChildren = new ArrayList<>();
        
        if (children != null && !children.isEmpty()) {
            for (TreeNode<T> child : children) {
                N childNode = (N) child;
                N filteredChild = filterNode(childNode, predicate);
                if (filteredChild != null) {
                    filteredChildren.add(filteredChild);
                }
            }
        }
        
        // 如果当前节点匹配条件，或者有匹配的子节点，则保留
        boolean nodeMatches = predicate.apply(node);
        boolean hasMatchingChildren = !filteredChildren.isEmpty();
        
        if (nodeMatches || hasMatchingChildren) {
            // 创建节点副本并设置过滤后的子节点
            try {
                N filteredNode = (N) BeanUtils.newInstance(node.getClass());
                BeanUtils.copyProperties(node, filteredNode);
                filteredNode.setChildren((List<? extends TreeNode<T>>) filteredChildren);
                return filteredNode;
            } catch (Exception e) {
                // 如果无法创建副本，直接修改原节点
                node.setChildren((List<? extends TreeNode<T>>) filteredChildren);
                return node;
            }
        }
        
        return null;
    }
    
    /**
     * 验证树形结构的完整性
     */
    public static <T, N extends TreeNode<T>> boolean validateTree(List<N> allNodes) {
        if (allNodes == null || allNodes.isEmpty()) {
            return true;
        }
        
        Set<T> allIds = allNodes.stream()
            .map(TreeNode::getId)
            .collect(Collectors.toSet());
        
        // 检查是否有重复ID
        if (allIds.size() != allNodes.size()) {
            return false;
        }
        
        // 检查父子关系是否有效
        for (N node : allNodes) {
            T parentId = node.getParentId();
            if (parentId != null && !allIds.contains(parentId)) {
                return false; // 父节点不存在
            }
            
            // 检查是否存在循环引用
            if (hasCircularReference(allNodes, node.getId(), new HashSet<>())) {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 检查是否存在循环引用
     */
    private static <T, N extends TreeNode<T>> boolean hasCircularReference(List<N> allNodes, T nodeId, Set<T> visited) {
        if (visited.contains(nodeId)) {
            return true; // 发现循环
        }
        
        visited.add(nodeId);
        
        // 查找当前节点
        N currentNode = allNodes.stream()
            .filter(node -> nodeId.equals(node.getId()))
            .findFirst()
            .orElse(null);
        
        if (currentNode != null && currentNode.getParentId() != null) {
            return hasCircularReference(allNodes, currentNode.getParentId(), visited);
        }
        
        visited.remove(nodeId);
        return false;
    }
}
